OPINION

FLOYD, Circuit Judge:

Appellants (the Inmates), eleven inmates in the custody of the Virginia Department of Corrections (DOC), brought this action against members of the Virginia Parole Board (the Board) in their official capacities. The Inmates contend that the Board has adopted policies and procedures with respect to parole-eligible inmates imprisoned for violent offenses that violate the Due Process and Ex Post Facto Clauses of the United States Constitution. Most notably, they assert that the Board has implemented an unwritten policy of denying parole to persons incarcerated for violent offenses. The district court granted Appellees' motion to dismiss the complaint, and the Inmates filed this timely appeal. Because we agree that the complaint fails to set forth sufficient facts to establish a plausible entitlement to relief under either a due process or ex post facto theory, we affirm.

I.

A.

Prior to 1994, Virginia law provided for discretionary parole1 of incarcerated offenders. By legislation enacted in 1994, the General Assembly abolished discretionary parole for all persons incarcerated for felony offenses committed on or after January 1, 1995. See Va.Code Ann. § 53.1-165.1. This legislation did not disrupt the availability of discretionary parole for persons who committed crimes prior to 1995, however.

The Virginia Code entrusts the administration of the discretionary parole system to the Board, and it vests the Board with broad discretion in carrying out its responsibilities. Section 53.1-136 of the Code obligates the Board to "[a]dopt ... general rules governing the granting of parole and eligibility requirements, which shall be published and posted for public review." Id. § 53.1-136(1). And this section further instructs that the Board "shall ... [r]elease on parole" parole-eligible persons who "are found suitable for parole, according to those rules" adopted by the Board. Id. § 53.1-136(2)(a). But the Board may not release any person without first conducting a "thorough investigation ... into the prisoner's history, physical and mental condition and character and his conduct, employment and attitude while in prison" and "determin[ing] that his release on parole will not be incompatible with the interests of society or of the prisoner." Id. § 53.1-155(A). As a general rule, the Board must consider parole-eligible inmates on an annual basis, but it may defer subsequent review for up to three years if an inmate has at least ten years remaining on his sentence. Id. § 53.1-154.

In addition to discretionary parole, Virginia has a system of conditional release for geriatric prisoners, which it instituted in 1995. See id. § 53.1-40.01. This program is available to prisoners (i) ages sixty-five or older who have served at least five years of their imposed sentences or (ii) ages sixty or older who have served as least ten years of their imposed sentences. Id. Again, the Virginia Code grants the Board discretion to promulgate regulations implementing the geriatric release program. See id. The Board's written policy permits it to release an inmate under the geriatric release program only upon a finding of "compelling reasons."

B.

The Inmates allege that, since the abolition of parole for new felony offenders in 1995, the Board has instituted policies and procedural changes that effect a de facto abolition of parole for parole-eligible persons convicted of violent offenses, defined in the complaint as "murder, rape, sodomy, robbery, assault, abduction, use of a weapon, and any other felony that the Board considers to be violent."

As the Inmates observe, the Board has ceased utilizing a risk assessment tool that was in use prior to 1995. In addition, the Board has eliminated face-to-face interviews of prisoners by Board members, supplanting them with interviews, often via video, by parole examiners who then submit reports to the Board through an electronic database. Board members also have stopped meeting in person; instead, they circulate an inmate's file before voting electronically to grant or deny parole. And, pursuant to a 2002 rule change, the Board has decreased the frequency of its meetings with inmates' families and representatives, who now may schedule such meetings no more than once every two years and may meet with only one of the five Board members.

In addition to these procedural changes, the Inmates note that, in 1998, the Board repealed prior rules governing parole that it had published in the Virginia Administrative Code. In place of these rules, it distributed a "Policy Manual." This Manual outlines fourteen factors that, according to the Board, guide its discretion in parole decisions. The nature of the offense of incarceration is one such factor, along with considerations of rehabilitation and the risk posed by the prisoner to himself and to society upon his release.

Despite the multiplicity of factors identified in this Manual, the Inmates allege that, in practice, the Board "has relied primarily, if not exclusively, on the `serious nature and circumstances of the crime' when making parole determinations with regard to inmates convicted of violent offenses" and has failed to give "fair or meaningful consideration to other factors in its Policy Manual." They claim that the Board's procedural changes reflect its choice to consider only the nature of the original offense. The exclusive reliance on this consideration, the Inmates aver, "has resulted in virtually automatic and repeated denials of parole for inmates convicted of violent offenses, even when the other factors in the Manual and the statute would favor release."

C.

The Inmates cite extensive statistical evidence to support their claim of a de facto abolition of parole for those convicted of violent offenses. Prior to the elimination of discretionary parole for new offenders, they note, Virginia's parole-grant rate — the percentage of those considered who were granted parole — exceeded 40%. In 1989, 42% of those considered were released on parole, and from 1990 to 1993, the parole-grant rate averaged over 41%. As a result of this relatively high grant rate, offenders generally did not serve the entire length of their sentences: in 1993, a person convicted of a violent offense in Virginia served, on average, only 38% of his total sentence. And, according to the Inmates, these numbers led participants in the court system, including defendants and sentencing judges, to anticipate early release.

Since 1995, however, Virginia has seen a precipitous decrease in the parole-grant rate. The rate for all parole-eligible inmates dipped to 18% in fiscal year (FY) 1996. It further declined to 8% in FY 2000 and to less than 5% in FY 2008. Violent offenders face still lower parole-grant rates: the rate for inmates convicted of violent offenses ranged between 3.7% and 2.1% per year from FY 2002 to FY 2008. And many of those granted parole were nearing their mandatory parole release dates, often having "already served more than 85% of the time before their mandatory parole release date[s]."

The Inmates contend that one factor, the seriousness of the offense, has played the primary or exclusive role in motivating the Board to deny parole to violent offenders. In FYs 2006 and 2007, for example, the Board cited "`the serious nature and circumstances of the crime' or words to that effect" as the sole reason for its decision in approximately 45% of all parole denials.

According to the Inmates, this focus on the seriousness of the offense has also infected the Board's administration of the geriatric release program. They allege that since the program went into effect in 1995, the Board has granted only seven geriatric release petitions. And it has named the serious nature of the original offense as the reason for 95% of the denials.

D.

The Inmates2 are among those parole-eligible inmates convicted of violent offenses committed prior to January 1, 1995, who have been denied parole. Each was convicted of at least one count of murder. Their sentences range from eighty years' imprisonment to multiple life terms, and each has served at least twenty-three years of his or her term of imprisonment. While in prison, many of the Inmates have successfully completed or participated in rehabilitative, vocational, educational, or employment programs. Yet despite their largely positive institutional records and limited prior criminal records, the Board has denied parole to each Inmate on multiple occasions.

The Inmates allege the following with respect to their individual histories and experiences with the Board:

In sum, the Inmates claim that, in evaluating a prisoner for parole, the Board has replaced fair and meaningful review of the fourteen Policy Manual factors with consideration of only one factor, the offense for which the prisoner is incarcerated. Thus, they assert that their limited prior criminal histories and generally outstanding institutional records cannot alter the outcome of the Board's determination because, for certain violent crimes, the Board has replaced the exercise of discretion with the automatic denial of parole. According to the Inmates, the Board fails to consider violent offenders as individuals; instead, it effectively applies the 1994 legislative changes retroactively to eliminate discretionary parole for parole-eligible violent offenders.

II.

The Inmates brought suit, asserting that the Board's policy changes — particularly its alleged de facto abolition of parole — violate their rights under the Due Process Clause and the Ex Post Facto Clause of the United States Constitution. The district court granted the Board's motion to dismiss the complaint.

Analyzing the due process claim, the district court first recognized that the Inmates have a limited constitutional interest in parole consideration derived from Virginia law. But the court found that the complaint's allegations showed that the Board afforded the Inmates sufficient process to satisfy this interest by providing each Inmate with a constitutionally valid reason for the denial of parole.

In addition, the district court found that the complaint's factual allegations failed to support the conclusion that the Board has effectively eliminated parole for inmates convicted of violent offenses. Of note, the Inmates' statistical evidence showed that in 55% of cases the denial of parole was based on reasons other than just the serious nature and circumstances of the original offense. Moreover, according to this data, the Board continued to parole between 120 and 230 violent offenders each year, demonstrating that parole remained attainable for such inmates. And the dwindling parole-grant rates could be explained by the shrinking pool of parole-eligible individuals. The district court reasoned that those persons best suited for parole were released each year, but due to the abolition of discretionary parole for new felony offenders, no new inmates were becoming eligible for parole. Hence, each year the Board considered a smaller pool of potential parolees, less suitable for release than those considered in the past. The allegations, the district court concluded, failed to state a plausible claim for a due process violation.

The district court likewise found the Inmates' allegations with respect to the Ex Post Facto Clause lacking. The Inmates' statistical allegations undermined their assertion that the Board has imposed a de facto rule precluding inmates convicted of violent offenses from parole. Thus, the district court concluded that, at most, the Inmates were complaining that the Board had become harsher in exercising its discretion, and because the relevant statutes had always authorized the Board to adopt a stricter stance, the pleadings were insufficient to support an ex post facto claim.

III.

"We review de novo a district court's decision to dismiss for failure to state a claim, assuming all well-pleaded, nonconclusory factual allegations in the complaint to be true." Aziz v. Alcolac, Inc., 658 F.3d 388, 391 (4th Cir.2011). To survive a Rule 12(b)(6) motion, a complaint must allege facts sufficient "`to raise a right to relief above the speculative level,' thereby `nudg[ing] the[ ] claims across the line from conceivable to plausible.'" Id. (first alteration in original) (quoting Bell Atl. Corp. v. Twombly, 550 U.S. 544, 555, 570, 127 S.Ct. 1955, 167 L.Ed.2d 929 (2007)). "Where a complaint pleads facts that are `merely consistent with' a defendant's liability, it `stops short of the line between possibility and plausibility of entitlement to relief.'" Ashcroft v. Iqbal, 556 U.S. 662, 678, 129 S.Ct. 1937, 173 L.Ed.2d 868 (2009) (quoting Twombly, 550 U.S. at 557, 127 S.Ct. 1955).

In undertaking this review, although we must accept the truthfulness of all factual allegations, we need not assume the veracity of "bare legal conclusions." Aziz, 658 F.3d at 391. Therefore, like the district court, we begin our analysis by differentiating between the Inmates' factual allegations and legal conclusions. The allegations with respect to the statistics on parole release and the Inmates' histories and experiences with the Board are factual. As such, we accept them as true. But we will accept the conclusions the Inmates draw from these facts — that the Board has ceased exercising its discretion and, instead, denies parole automatically due to the crime of incarceration — only to the extent they are plausible based on the factual allegations.

A.

The Fourteenth Amendment's Due Process Clause guards against unlawful deprivations of life, liberty, or property. U.S. Const. amend. XIV, § 1. Thus, in analyzing the Inmates' due process claim, we first must consider whether, and to what extent, they have a protectible interest under this Clause. See Greenholtz v. Inmates of the Neb. Penal & Corr. Complex, 442 U.S. 1, 7, 99 S.Ct. 2100, 60 L.Ed.2d 668 (1979); Slezak v. Evatt, 21 F.3d 590, 594 (4th Cir.1994). If the Inmates have asserted a protectible interest, we then determine whether they have sufficiently alleged that the Commonwealth failed to afford them the minimum procedural protections required by the Fourteenth Amendment in depriving them of this interest. See Morrissey v. Brewer, 408 U.S. 471, 481, 92 S.Ct. 2593, 33 L.Ed.2d 484 (1972); Slezak, 21 F.3d at 593.

"A liberty interest may arise from the Constitution itself" or "from an expectation or interest created by state laws or policies." Wilkinson v. Austin, 545 U.S. 209, 221, 125 S.Ct. 2384, 162 L.Ed.2d 174 (2005). An "abstract ... desire" or "unilateral expectation" is insufficient to create a protectible interest. Greenholtz, 442 U.S. at 7, 99 S.Ct. 2100 (quoting Bd. of Regents of State Colls. v. Roth, 408 U.S. 564, 577, 92 S.Ct. 2701, 33 L.Ed.2d 548 (1972)) (internal quotation marks omitted). Rather, the Due Process Clause protects only those interests to which an individual has a "legitimate claim of entitlement." Id. (quoting Roth, 408 U.S. at 577, 92 S.Ct. 2701) (internal quotation marks omitted). It is well-established in the context of parole that "[t]here is no constitutional or inherent right of a convicted person to be conditionally released before the expiration of a valid sentence." Id. Accordingly, to the extent the Inmates enjoy a protectible interest in parole, this interest must find its roots in rights imparted by Virginia law.

The Inmates assert, and the Board concedes, that Virginia law gives rise to a limited interest in consideration for parole, but not in parole release. Specifically, the Virginia Code mandates that the Board must adopt rules governing the granting of parole and eligibility for parole and that it must release eligible persons who it finds suitable for parole under these rules. Va.Code Ann. § 53.1-136(1)-(2)(a). Because the decision whether to grant parole is a discretionary one, "a prisoner cannot claim entitlement and therefore a liberty interest in the parole release." Gaston v. Taylor, 946 F.2d 340, 344 (4th Cir.1991) (en banc); see also Vann v. Angelone, 73 F.3d 519, 522 (4th Cir.1996). This is true even if state officials consistently have exercised their discretion to grant release in the past: "A constitutional entitlement cannot be created ... merely because a wholly and expressly discretionary state privilege has been granted generously in the past." Hill v. Jackson, 64 F.3d 163, 170 (4th Cir.1995) (quoting Conn. Bd. of Pardons v. Dumschat, 452 U.S. 458, 465, 101 S.Ct. 2460, 69 L.Ed.2d 158 (1981)) (internal quotation marks omitted). But, as the Board acknowledges, state law "giv[es] to a [parole-eligible] prisoner the right for parole consideration at a specified time." Gaston, 946 F.2d at 344; see also Hill, 64 F.3d at 170.

Once a state has "create[d] a liberty interest, the Due Process Clause requires fair procedures for its vindication." Swarthout v. Cooke, ___ U.S. ___, 131 S.Ct. 859, 862, 178 L.Ed.2d 732 (2011) (per curiam). Thus, although a state is under no obligation to offer parole, once it has done so, we "will review the application of [these] constitutionally required procedures." Id. But we are hard-pressed "to imagine a context more deserving of federal deference than state parole decisions." Vann, 73 F.3d at 521. Thus, in the parole context, "the procedures required are minimal." Swarthout, 131 S.Ct. at 862.

In prior challenges to Virginia's discretionary parole system, we determined that, "[a]t most, ... parole authorities must `furnish to the prisoner a statement of its reasons for denial of parole.'" Vann, 73 F.3d at 522 (quoting Franklin v. Shields, 569 F.2d 784, 801 (4th Cir.1978) (en banc)). Beyond this, we have declined to hold that, as a constitutional matter, each prisoner must "receive a personal hearing, have access to his files, or be entitled to call witnesses in his behalf to appear before the Board." Franklin, 569 F.2d at 800.

The Inmates acknowledge that each time they were denied parole, the Board provided a reason or reasons for its denial. Typically, the reason given has been "`the serious nature and circumstances of the crime' or words to that effect." The Inmates concede that this is a valid reason for the denial of parole. Moreover, although they object to a number of procedural changes that have occurred since the abolition of discretionary parole in 1995, the Inmates had no entitlement to the individual procedures.

The Inmates nonetheless assert that the Board has denied them due process because it has failed to consider them for parole in a fair and meaningful manner. That is, they argue that the Board has disregarded its statutory mandate by failing to determine whether a prisoner is suitable for parole through an individual analysis of the factors identified in the Policy Manual. They contend the Board, instead, has established a de facto rule denying parole to persons imprisoned for violent offenses.

This argument falters, however, because the facts alleged in the complaint do not plausibly support this conclusion. As the district court ably explained, the statistical allegations show that the Board continues to grant parole to violent offenders, though at lower rates than in the past. The Inmates allege that in each year from FY 2002 through FY 2008, the Board released on parole between 3.7% and 2.1% of parole-eligible inmates incarcerated for violent offenses. This correlates to between 120 and slightly more than 230 inmates per year. In addition, according to the complaint, the seriousness of the offense was the sole reason given in 45% of parole denials, meaning that in more than half of denials the Board provided another reason — either instead of or in addition to this factor — to explain its decision.

These facts indicate that the Board was making individual determinations with respect to violent offenders. It was releasing numerous such offenders despite the crimes of which they were convicted. And, in many cases, it was not only considering but also relying on reasons other than the seriousness of the crime and its attendant circumstances in deciding to deny parole.

The Inmates have suggested that the Board is considering illegitimate factors in deciding to release some violent offenders but not others. They have offered only speculation in support of this view, however. In the absence of facts to the contrary, we cannot presume that the Board has failed to conform to constitutional requirements and its statutory mandate, see Garner v. Jones, 529 U.S. 244, 256, 120 S.Ct. 1362, 146 L.Ed.2d 236 (2000). Here, the Inmates' statistical allegations fail to provide the necessary facts.

The allegations regarding the Inmates' individual circumstances fare no better. According to the complaint, each of the Inmates had little or no criminal history at the time of his or her conviction of the offense of incarceration, and many have demonstrated consistently excellent institutional behavior. Many have successfully participated in rehabilitative, educational, vocational, or like programs while in prison. Some have garnered the support of counselors, DOC officers, and others in seeking parole. Nevertheless, the Board has refused to release them based on the seriousness of their crimes. Indeed, for eight of the eleven Appellants, this factor, the "serious nature and circumstances of the crime" (or like words), has been the sole reason given in explaining repeated parole denials.3

Yet we cannot infer from these facts that the Board is failing to consider each Inmate individually, according to the relevant factors, when making these parole determinations. Each of the Inmates was convicted of a very serious crime or crimes, for which he or she received a lengthy sentence. It appears from the complaint that the lightest sentence given to any of the Inmates was eighty years' imprisonment. It would be well within the Board's discretion to consider such a prisoner holistically and nevertheless to determine that he or she has not served a sufficiently lengthy sentence in light of the grave crime, notwithstanding an otherwise clear criminal history and superlative institutional conduct. Although the ultimate result of this decisionmaking process would be to deny parole based solely on the seriousness of the prisoner's crime, the process and decision would comply fully with constitutional demands.

Here, the factual allegations do not demonstrate that the Board has replaced this type of individual consideration with a de facto rule rejecting violent offenders. Simply put, the Board's declination to grant parole to the Inmates — even repeatedly — based on the seriousness of their offenses cannot show that it has failed to consider other factors.4

Ultimately, the Inmates have presented only speculation that the Board has imposed a bar against parole for violent offenders. But without factual allegations supporting such an inference, we cannot presume that the Board is failing to "follow[] its statutory commands and internal policies in fulfilling its obligations." Id. The Inmates, therefore, have failed to show a plausible entitlement to relief as required under the Iqbal-Twombly pleading standard.5 Consequently, we will affirm the district court's dismissal of the due process claim.

B.

The Inmates next assert that the Board has effected an ex post facto enhancement of the punishment for their crimes, in violation of the United States Constitution. This claim, too, falls short.

The Ex Post Facto Clause prevents a state from "pass[ing] any `ex post facto Law.'" Warren v. Baskerville, 233 F.3d 204, 207 (4th Cir.2000) (quoting U.S. Const. art. I, § 10, cl. 1). Among other things, this Clause "bar[s] enactments which, by retroactive operation, increase the punishment for a crime after its commission." Garner, 529 U.S. at 249-50, 120 S.Ct. 1362. To state a claim for a violation of this provision, a plaintiff must plead facts showing the retroactive application of a new rule that "by its own terms" or through "practical implementation" creates a "significant risk" of extending the period of incarceration to which he is subject. Id. at 255, 120 S.Ct. 1362.

Assuming the Ex Post Facto Clause applies to the Board's policy changes,6 the Inmates have failed to identify a new policy creating a significant risk of increased punishment. Their complaint identifies a variety of changes to parole review procedures, including the Board's decisions to cease using a risk assessment tool, to enlist parole examiners to perform interviews, and to vote electronically. But the Inmates have failed to plead facts showing a causal link between these procedural changes and a significant risk of extended punishment.

By their terms, these procedures do not impact the length of the Inmates' period of imprisonment, so the Inmates must point to the implementation of the procedures. Although the Inmates complain that parole-grant rates have decreased since 1995, they have not alleged facts demonstrating that this decrease may be ascribed to any procedural change. The mere fact that the Board implemented these procedural changes during the same multi-year period that the rate decreased does not produce a plausible inference of a causal connection, particularly as there are numerous other explanations for the decreasing parole-grant rate. As the district court noted, some of this decrease may be understood to reflect the shrinking pool of eligible offenders, who the Board may have found to be less suitable for parole. More notably, the Inmates themselves press an alternative reason for the declining parole-grant rate: they urge that instead of following its statutory mandate to determine suitability for parole based on the multifarious factors identified in the Policy Manual, the Board has adopted a policy of refusing parole to violent offenders based solely on their offenses. And the complaint cites the Board's procedural changes as evidence that the Board is disregarding other relevant factors.

It is this alleged policy change — the de facto abolition of discretionary parole — that is at the crux of the Inmates' complaint. But, as discussed with respect to the Inmates' due process claim, it is implausible based on the facts alleged that the Board has adopted any such policy. The factual allegations suggest that the Board has become harsher with respect to violent offenses, but they do not indicate that the Board has implemented a de facto prohibition of parole for persons convicted of these offenses. In the absence of such facts, we cannot reasonably infer that the Board is failing to exercise its discretion as required by state law. See Garner, 529 U.S. at 256, 120 S.Ct. 1362.

Ultimately, the Inmates' complaint supports, at most, the inference that the Board is exercising its discretion, but that, in doing so, the Board is taking a stricter view towards violent offenders than it had in the past. This shift in the manner in which it exercises its discretion, however, does not implicate the Ex Post Facto Clause. As the Sixth Circuit has explained, where the statutory scope of a parole board's discretion is unchanged from the time a prisoner committed his offense, "there was always the possibility the Board would exercise its discretion in a way that would result in fewer paroles and longer prison terms." Foster v. Booker, 595 F.3d 353, 362 (6th Cir.2010). Inmates may have some ex post facto-protected interest in the rules that guide and govern the exercise of discretion, see Garner, 529 U.S. at 253, 120 S.Ct. 1362, but they do not have a protected interest in the exercise of discretion itself. Thus, that the Board may have decided "to get tougher" on certain crimes "hardly amount[s] to an ex post facto violation" because "it was within the ... Board's discretion to get tougher." Foster, 595 F.3d at 362.

We should not and will not "micromanage[]" state parole systems through the Ex Post Facto Clause. Warren, 233 F.3d at 208 (quoting Garner, 529 U.S. at 252, 120 S.Ct. 1362) (internal quotation marks omitted). In the instant action, the Inmates have alleged facts indicating only that, in exercising its discretion, the Board has opted to adopt a harsher tack with respect to violent offenders. This is not actionable.

IV.

We are sympathetic to the challenges faced by the Inmates in bringing these claims and the lack of information about the Board's internal workings at their disposal. Nevertheless, they are not relieved of their obligation under the Iqbal-Twombly pleading standard to allege facts demonstrating a plausible, not merely possible, entitlement to relief. Because they have failed to meet this obligation, dismissal of the complaint was appropriate. For this reason, we affirm the judgment of the district court.

AFFIRMED

GREGORY, J., dissenting:

The Court adheres today to a rigidly formalistic view of the Due Process Clause that provides no real protection for the well-established liberty interest Virginia inmates have in parole consideration. For this reason, I respectfully dissent.

I.

The majority and I are in agreement on several points. There is no independent due process right to parole, e.g., Greenholtz v. Inmates of the Neb. Penal & Correctional Complex, 442 U.S. 1, 7, 99 S.Ct. 2100, 60 L.Ed.2d 668 (1979), nor is there one in being considered for parole, Hill v. Jackson, 64 F.3d 163 (4th Cir.1995). However, a State can create such a liberty interest, id. at 170, and Virginia has done so here, vesting in its inmates a right to parole consideration through the passage of its parole statute, id. Finally, the Due Process Clause requires that the parole board ("the Board") furnish an inmate with a written explanation for its denial of parole. E.g., Bloodgood v. Garraghty, 783 F.2d 470, 473 (4th Cir.1986); Franklin v. Shields, 569 F.2d 784, 800 (4th Cir.1978) (en banc).

The majority and I part ways on the question of whether the Due Process Clause provides any additional protections to inmates, like the Appellants, who have a liberty interest in parole consideration. While a hyper-literal interpretation of this Court's precedent might suggest that nothing beyond a written explanation is required,1 we have never before held this to be the case,2 and we should not do so today.

While the majority cites to Franklin v. Shields, Bloodgood v. Garraghty, and Vann v. Angelone for the proposition that the Board need only furnish a written explanation for denial, these cases contemplated the Board doing more than applying one factor to every case it hears. In Bloodgood we held that we "will not assume that the Board relied on possibly invalid factors" in makings its decisions. Bloodgood, 783 F.2d at 475. This of course presupposes that there are invalid factors — that the Due Process Clause requires not just a written explanation for the denial, but that the denial be based on valid factors. In Vann, we recognized that parole consideration consists of more than the rote application of a single factor: "Most parole decisions involve a considerable degree of discretion. Hence, parole authorities must investigate and weigh numerous factors including [the inmate's] history, mental and physical condition, attitude, and compatibility with the `interests of society.'" Vann v. Angelone, 73 F.3d 519 (4th Cir.1996) (quoting Gaston v. Taylor, 946 F.2d 340, 344 (4th Cir.1991)). Similarly, in Bloodgood we said, "The board's inquiry is not the legal foundation of some past conviction, but a prediction of a prisoner's prospects for a law-abiding life." Bloodgood, 783 F.2d at 473 (citing Franklin, 569 F.2d at 800). Thus we have implied that the Board must consider at least some factors beyond the nature of the offense.

I emphasize the distinction between the question of whether a factor is valid and whether it is sufficient. The nature and circumstances of the underlying offense is indisputably a legitimate factor that may be considered, but it is not enough standing alone. The Due Process Clause requires that the Board consider additional factors as well. Whether the Due Process Clause requires that specific additional factors be considered, it is enough here to note that the Board and the State of Virginia have substantial discretion in determining how it will weigh the factors in making the final decision whether to grant parole. But to hold that the rote use of the nature of the underlying offense by itself is sufficient transmogrifies the parole process into an empty formality.

II.

The Appellants' complaint alleges facts that render plausible the inference that the Board only considers the nature and circumstances of the crime in deciding whether to grant or deny them parole. See Bell Atl. Corp. v. Twombly, 550 U.S. 544, 127 S.Ct. 1955, 167 L.Ed.2d 929 (2007). Appellants allege that after Virginia's General Assembly abolished parole for all newly incarcerated inmates in 1995, the Board instituted a number of changes to its procedures. Prior to 1995, the Board used a risk assessment tool in making parole determinations; but after the abolition of parole the Board discontinued use of the tool. J.A. 21. The Board has also abandoned its practice of conducting face-to-face interviews with parole-eligible inmates. J.A. 23. It has similarly discouraged wardens, guards, and other prison officials from providing it with information about eligible inmates, J.A. 23, and has decreased the frequency with which inmates' families appear before it, J.A. 24. The Board no longer meets in person regularly, but instead circulates electronic files and has its members cast votes to grant or deny parole electronically. J.A. 23-24. Virginia law requires the Board to establish rules to govern parole procedure. VA CODE § 53.1-136.1. While these used to be published in the Virginia Administrative Code, 14 Va. Reg. No. 17 at 2457 (Apr. 22, 1998), in 1998 the Board repealed those policies and has not replaced them; instead, it has adopted an informal "policy manual." J.A. 22. Perhaps most tellingly, the policy manual lists fourteen factors the Board is to consider in determining whether to grant parole, with rehabilitative concerns featuring prominently among them. J.A. 22. Nevertheless, the Appellants were denied parole in the vast majority of cases for one and only one reason — the nature and circumstances of the underlying offense. J.A. 22.3 The majority asserts that the Appellants have offered "only speculation in support of [their] view" that they are not being considered for parole. Maj. op. at 182-83. However, these significant procedural changes, taken together, strongly suggest the Board has systematically eliminated the procedures that would have furnished it with information beyond the nature and circumstances of the underlying offense. These allegations are sufficient to surmount the relatively low burden of surviving a 12(b)(6) motion to dismiss.

It is true that on rare occasions the Board gave a reason other than the nature and circumstances of the offense in denying some of the Appellants parole. But for each Appellant, the Board has relied on the nature and circumstances of the offense, and no other factor, on at least one occasion. Thus, assuming there is a constitutional violation when the Board fails to consider any other reason, see supra Part II, each Appellant has suffered a constitutional injury on multiple occasions.

III.

"Fundamental fairness [is] the touchstone of due process." Gagnon v. Scarpelli, 411 U.S. 778, 790, 93 S.Ct. 1756, 36 L.Ed.2d 656 (1973). In my view, fundamental fairness in the parole context requires at a minimum that the Board consider at least one factor beyond the nature of the underlying offense. The facts in the Appellants' complaint make out a plausible claim that the Board has failed to comply with this requirement. As such, I would vacate the district court's 12(b)(6) dismissal and remand for further proceedings.